Multicarrier communication systems such as discrete multitone (DMT) and OFDM systems have attracted much attention in the applications of high-speed communication. The advantages of the multicarrier communication system lie in partitioning a high speed data stream into a plurality of parallel data streams, each transmitted by a subcarrier. As such, each data stream is transmitted at low speed, and thus has a stronger capability in anti-multipath channel effect and narrow band interference.
FIG. 1 shows a block diagram of a conventional OFDM transmitter. In the OFDM transmitter, the input data X[k], k=0, 1, . . . , N−1, are transmitted in an OFDM symbol period, where N is the number of useful data in an OFDM symbol. After the serial/parallel transformation, N-point inverse fast Fourier transform (N-IFFT), and parallel/serial transformation, the input data are transformed into the following discrete time sequence:
                                                        x              ⁡                              [                n                ]                                      =                                          1                                  N                                            ⁢                                                ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                                      X                    ⁡                                          [                      k                      ]                                                        ⁢                                      W                    N                    kn                                                                                ,                                          ⁢                      n            =            0                    ,          1          ,          …          ⁢                                          ,                      N            -            1                          ⁢                                  ⁢        where                            (        1        )                                          W          N                ≡                  ⅇ                      j2π            /            N                                              (        2        )            is the twiddle factor. The discrete time sequence x[n] obtained from equation (1) undergoes the cyclic prefix insertion and digital/analog transformation to obtain an analog signal x(t). The analog signal x(t) is then transmitted to the RF front end for further processing, including an IQ modulation, an up conversion, and a power amplification. The PAPR of the analog signal x(t) is several dB higher than the PAPR of the corresponding discrete time sequence x[n], and is close to the PAPR of x[n/R]. where x[n/R] represents the sequence obtained by R times oversampling of x[n]. Therefore, the PAPR of x(t) can be approximated by using x[n/R] as follows:
                    PAPR        =                                            max                              0                ≤                n                ≤                                  RN                  -                  1                                                      ⁢                                                                            x                  ⁡                                      [                                          n                      /                      R                                        ]                                                                              2                                            E            ⁢                          {                                                                                      x                    ⁡                                          [                                              n                        /                        R                                            ]                                                                                        2                            }                                                          (        3        )            Where E{·} is the expectation operation. The approximation is relatively accurate when R≧4. However, one of the main disadvantages of multicarrier communication systems is the high PAPR of the modulated signal. When the modulated signal with a high PAPR passes through the RF front end, the signal is distorted due to the non-linearity of a regular RF amplifier. The non-linearity not only causes the in-band signal distortion which leads to the increase of the bit error rate (BER), but also causes the out-of-band radiation which leads to the interference of adjacent channels, a violation of the government regulation. A straightforward solution to this problem would be using an RF amplifier with a larger linear range. However, the aforementioned solution will lead to the reduction of power efficiency, higher power consumption and a higher manufacturing cost.
There are several conventional methods for solving the aforementioned problem. Among these methods, the partial transmit sequences (PTS) is most attractive due to its relatively low realization complexity and capability in PAPR reduction. Ericsson (U.S. Pat. No. 6,125,103) disclosed a method for using PTS to solve the high PAPR of the signal at the OFDM transmission end, as shown in FIG. 2. The explanation is as follows.
First, the input data X[k] of length N is partitioned in the frequency domain into M disjoint subblocks, represented by X1[k], X2[k], . . . , XM[k], k=0, 1, . . . , N−1. The partition can be interleaved, adjacent, or irregular, as shown in FIG. 3 (using M=8 as an example). The M disjoint subblocks are phase-rotated and added to form the following signal:
                                                        X              ~                        ⁡                          [              k              ]                                =                                    ∑                              m                =                1                            M                        ⁢                                          b                m                            ⁢                                                X                  m                                ⁡                                  [                  k                  ]                                                                    ,                                  ⁢                  k          =          0                ,        1        ,                                  ⁢        …        ⁢                                  ,                  N          -          1                                    (        4        )            where bm is the phase rotation parameter of the m-th subblock (mε{1, 2, . . . , M}) and |bm|=1.Equation (4), after the N-IFFT, becomes:
                                                        x              ~                        ⁡                          [              n              ]                                =                                    ∑                              m                =                1                            M                        ⁢                                          b                m                            ⁢                                                x                  m                                ⁡                                  [                  n                  ]                                                                    ,                                  ⁢                  n          =          0                ,        1        ,        …        ⁢                                  ,                  N          -          1                                    (        5        )            where xm[n] is the result of the N-IFFT of the Xm[k]. In the PAPR reduction, the object of the PTS method is the phase optimization, i.e., seeking for the optimal sequence {b1, b2, . . . , bM} so that the PAPR of the transmitted signal is minimum. In practice, the phase of bm is usually restricted to one of the four possibilities {+1, −1, +j, −j} so that no multiplication operation is required in the phase rotation.
From FIG. 2, it can be seen that an N-point OFDM symbol requires M times of N-IFFT operation. That is, a total of M·(N/2)log2 N complex multiplications are required. Several methods are further devised to reduce the amount of computation required in the PTS method. Kang, Kim and Joo, in their article “A Novel Subblock Partition Scheme for Partial Transmit Sequence OFDM,” IEEE Trans. Broadcasting, vol. 45, no. 3, pp. 333-338, September 1999, disclosed a method of using the characteristics of the PTS interleaved partition of the subblocks, as shown in FIG. 4 (M=8). Each subblock has N points in the frequency domain, but only L points of them have non-zero values (L=N/M). Therefore, the N-IFTT on the N-point subblock Xm[k] is equivalent to the L-IFFT on the L-point subblock (where Xm[k] has non-zero values), repeating M times in the time domain to form the N-point signal, and multiplying the N-point signal with the N-point complex coefiicients:(1/M)·ej2πmn/N, m=0, 1, . . . , M−1, n=0, 1, . . . , N−1This method takes M·(L/2)log2 L+MN multiplications, and requires MN units of memory space.
Samsung (US. Patent publication 2003/0,067,866) disclosed a similar method, as shown in FIG. 5. The Samsung method differs from the previous method in no repetition after the L-IFFT on an L-point subblock. Instead, the multiplication of the L-point complex coefficients in the time domain is performed to make the time domain subblocks orthogonal so that the receiving end can separate each subblock. As there are only L points in each time domain subblock, the PAPR is lower and, therefore, the PAPR of the transmitted signal after the phase rotation and the addition is also lower. Although this method takes M·(L/2)log2 L+N multiplications and requires N units of memory space, this method reduces the length of the OFDM signal from N to L, which means that the capability of anti-multipath channel effect is also greatly reduced. Furthermore, the L-point complex coefficient multiplier to make the time domain subblocks orthogonal is hard to design and may not exist for most applications. This will further make the receiving end more difficult in obtaining the original transmitted data.